//
//  BSTree.hpp
//  BSTree
//
//  Created by Shane on 17/9/22.
//  Copyright © 2017年 Shane. All rights reserved.
//

#ifndef BSTree_hpp
#define BSTree_hpp

#include <iostream>
#include "BSTNode.hpp"
#include <stack>
using namespace std;

enum Tag{left, right};


template <class T>
class BSTree {
public:
    BSTree(){
//        m_size = 0;
    };
    ~BSTree(){};
public:
    //前序遍历
    void preOrder();
    //中序遍历
    void inOrder();
    //后序遍历
    void postOrder();
    
    //插入结点
    void insert(T key);
    //删除结点
    bool remove(T key);
    //查找节点
    BSTNode<T>* search(T key);
    
    //最小值和最大值
    T minimum();
    T maximum();
    
    //节点的前驱和后继
    BSTNode<T>* predecessor(T key);
    BSTNode<T>* sucessor(T key);
    
    //销毁树
    void destroy();
    
    //返回节点数
    int size();
    //返回叶子节点数
    int leaf();
    //返回树的高度
    int height();
private:
    //前序遍历  递归方式和非递归方式
    void preOrderWithRecursive(BSTNode<T> *root) const;
    void preOrderWithoutRecursive(BSTNode<T> *root) const;
    
    //中序遍历  递归方式和非递归方式
    void inOrderWithRecursive(BSTNode<T> *root) const;
    void inOrderWithoutRecursive(BSTNode<T> *root) const;
    
    //后序遍历
    void postOrderWithRecursive(BSTNode<T> *root) const;
    
    //查找节点  递归方式和非递归方式
    BSTNode<T>* searchWithRecursive(BSTNode<T> *root, T key) const;
    BSTNode<T>* searchWithoutRecursive(BSTNode<T> *root, T key) const;
    
    //查找最小结点  最大结点
    BSTNode<T>* minumum(BSTNode<T> *root) const;
    BSTNode<T>* maximum(BSTNode<T> *root) const;
    
    //节点的前驱和后继
    BSTNode<T>* predecessor(BSTNode<T> *root, T key);
    BSTNode<T>* sucessor(BSTNode<T> *root, T key);
    
    //删除节点
    BSTNode<T>* remove(BSTNode<T>* &root, BSTNode<T> *node);
    
    //销毁树
    void destroy(BSTNode<T> *root);
    
    //树的高度
    int height(BSTNode<T> *root) const;
    
    //节点数
    int size(BSTNode<T> *root) const;
    
    //节点数
    int leaf(BSTNode<T> *root) const;
    
    
private:
    BSTNode<T> *m_root;
//    int m_size;
};


//前序遍历
template <class T>
void BSTree<T>::preOrder(){
    preOrderWithRecursive(m_root);
    std::cout << endl;
    preOrderWithoutRecursive(m_root);
    std::cout << endl;
}

template <class T>
void BSTree<T>::preOrderWithRecursive(BSTNode<T> *root) const{
    if (root) {
        std::cout << root->data << "\t";
        preOrderWithRecursive(root->leftChild);
        preOrderWithRecursive(root->rightChild);
    }
}

template <class T>
void BSTree<T>::preOrderWithoutRecursive(BSTNode<T> *root) const{
    std::stack<BSTNode<T> *> aStack;
    BSTNode<T> *pointer = root;
    while (!aStack.empty() || pointer) {
        if (pointer) {
            std::cout << pointer->data << "\t";
            aStack.push(pointer);
            pointer = pointer->leftChild;
        }else{
            pointer = aStack.top();
            aStack.pop();
            pointer = pointer->rightChild;
        }
    }
}


//中序遍历
template <class T>
void BSTree<T>::inOrder(){
    inOrderWithRecursive(m_root);
    std::cout << endl;
    inOrderWithoutRecursive(m_root);
    std::cout << endl;
}

template <class T>
void BSTree<T>::inOrderWithRecursive(BSTNode<T> *root) const{
    if (root) {
        inOrderWithRecursive(root->leftChild);
        std::cout << root->data << "\t";
        inOrderWithRecursive(root->rightChild);
    }
}

template <class T>
void BSTree<T>::inOrderWithoutRecursive(BSTNode<T> *root) const{
    BSTNode<T> *pointer = root;
    std::stack<BSTNode<T> *> aStack;
    while (!aStack.empty() || pointer) {
        if (pointer) {
            aStack.push(pointer);
            pointer = pointer->leftChild;
        }else{
            pointer = aStack.top();
            aStack.pop();
            std::cout << pointer->data << "\t";
            pointer = pointer->rightChild;
        }
    }
}

//后序遍历
template <class T>
void BSTree<T>::postOrder(){
    postOrderWithRecursive(m_root);
    std::cout << endl;
//    inOrderWithoutRecursive(m_root);
//    std::cout << endl;
}

template <class T>
void BSTree<T>::postOrderWithRecursive(BSTNode<T> *root) const{
    if (root) {
        postOrderWithRecursive(root->leftChild);
        postOrderWithRecursive(root->rightChild);
        std::cout << root->data << "\t";
    }
}



//插入节点
template <class T>
void BSTree<T>::insert(T key) {
    BSTNode<T> *node = new BSTNode<T>(key);
    if (!m_root) { //如果是一棵空树，则直接赋值给根结点
        m_root = node;
    }else{
        BSTNode<T> *pointer = m_root;
        BSTNode<T> *parent = nullptr;
        while (pointer) {
            parent = pointer;
            if (pointer->data > key) {
                pointer = pointer->leftChild;
            }else {
                pointer = pointer->rightChild;
            }
        }
        if (parent->data > key) {
            parent->leftChild = node;
        }else{
            parent->rightChild = node;
        }
        node->parent = parent;
    }
}

//删除节点
template <class T>
bool BSTree<T>::remove(T key){
    BSTNode<T> *node1, *node2;
    if ((node1 = search(key)) != nullptr) {
        if ((node2 = remove(m_root, node1)) != nullptr) {
            delete node2;
            return true;
        }
    }
    return false;
}

template <class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T> *&root, BSTNode<T> *node){
    BSTNode<T> *y = nullptr, *x = nullptr;
    if (node->leftChild == nullptr || node->rightChild == nullptr) {
        y = node;
    }else{
        y = sucessor(node->data);
    }
    
    if (y->leftChild != nullptr) {
        x = y->leftChild;
    }else{
        x = y->rightChild;
    }
    
    if (x != nullptr) {
        x->parent = y->parent;
    }
    
    if (y->parent == nullptr) {
        root = x;
    }else if (y == y->parent->leftChild){
        y->parent->leftChild = x;
    }else{
        y->parent->rightChild = x;
    }
    
    if (y != node) {
        node->data = y->data;
    }
    return y;
    
}

//查找节点
template <class T>
BSTNode<T>* BSTree<T>::search(T key){
//    return searchWithoutRecursive(m_root, key);
    return searchWithRecursive(m_root, key);
}

template <class T>
BSTNode<T>* BSTree<T>::searchWithRecursive(BSTNode<T> *root, T key)const {
    if (root == nullptr || root->data == key) {
        return root;
    }
    if (root->data > key){
        return searchWithRecursive(root->leftChild, key);
    }else{
        return searchWithRecursive(root->rightChild, key);
    }
}

template <class T>
BSTNode<T>* BSTree<T>::searchWithoutRecursive(BSTNode<T> *root, T key)const {
    BSTNode<T> *pointer = root;
    while (pointer) {
        if (pointer->data == key) {
            break;
        }else if (pointer->data > key){
            pointer = pointer->leftChild;
        }else{
            pointer = pointer->rightChild;
        }
    }
    return pointer;
}

//最小值和最大值
template <class T>
T BSTree<T>::minimum() {
    BSTNode<T> *pointer = minumum(m_root);
    return pointer ? pointer->data : INT_MIN;
}

template <class T>
T BSTree<T>::maximum() {
    BSTNode<T> *pointer = maximum(m_root);
    return pointer ? pointer->data : INT_MAX;
}

template <class T>
BSTNode<T>* BSTree<T>::minumum(BSTNode<T> *root) const{
    while (root->leftChild != nullptr) {
        root = root->leftChild;
    }
    return root;
}

template <class T>
BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *root) const{
    while (root->rightChild != nullptr) {
        root = root->rightChild;
    }
    return root;
}

//节点的前驱和后继
template <class T>
BSTNode<T>* BSTree<T>::predecessor(T key){
    return predecessor(m_root,key);
}

template <class T>
BSTNode<T>* BSTree<T>::sucessor(T key) {
    return sucessor(m_root, key);
}

template <class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *root, T key){
//    std::stack<BSTNode<T> *> aStack;
//    BSTNode<T> *pointer = node, *retNode = nullptr;
//    while (!aStack.empty() || pointer) {
//        if (pointer) {
//            aStack.push(pointer);
//            pointer = pointer->leftChild;
//        }else{
//            pointer = aStack.top();
//            aStack.pop();
//            if (pointer->data == key) {
//                return retNode;
//            }else{
//                retNode = pointer;
//            }
//            pointer = pointer->rightChild;
//        }
//    }
//    return retNode;
    BSTNode<T> *pointer = search(key);
    if (pointer) {
        if (pointer->leftChild) {
            return maximum(pointer->leftChild);
        }
        
        BSTNode<T> *aSucessor = pointer->parent;
        while (aSucessor && (pointer == aSucessor->leftChild)) {
            pointer = aSucessor;
            aSucessor = aSucessor->parent;
        }
        return aSucessor;
    }else{
        return nullptr;
    }
   
}

template <class T>
BSTNode<T>* BSTree<T>::sucessor(BSTNode<T> *root, T key){
//    std::stack<BSTNode<T> *> aStack;
//    BSTNode<T> *pointer = node, *retNode = nullptr;
//    while (!aStack.empty() || pointer) {
//        if (pointer) {
//            aStack.push(pointer);
//            pointer = pointer->leftChild;
//        }else{
//            pointer = aStack.top();
//            aStack.pop();
//            if (pointer->data == key) {
//                return pointer;
//            }
//            pointer = pointer->rightChild;
//        }
//    }
//    return retNode;
    BSTNode<T> *pointer = search(key);
    if (pointer) {
        if (pointer->rightChild) {
            return minumum(pointer->rightChild);
        }
        
        BSTNode<T> *aSucessor = pointer->parent;
        while (aSucessor && (pointer == aSucessor->rightChild)) {
            pointer = aSucessor;
            aSucessor = aSucessor->parent;
        }
        return aSucessor;

    }else{
        return nullptr;
    }
    
}

template <class T>
int BSTree<T>::leaf() {
    return leaf(m_root);
}

template <class T>
int BSTree<T>::leaf(BSTNode<T> *root) const{
//    int leafNum = 0;
//    BSTNode<T> *pointer = m_root;
//    std::stack<BSTNode<T> *> aStack;
//    while (!aStack.empty() || pointer) {
//        if (pointer) {
//            aStack.push(pointer);
//            pointer = pointer->leftChild;
//        }else{
//            pointer = aStack.top();
//            aStack.pop();
//            if (pointer->leftChild == nullptr && pointer->rightChild == nullptr) {
//                ++leafNum;
//            }
//            pointer = pointer->rightChild;
//        }
//    }
//    return leafNum;
    if (!root) {
        return 0;
    }
    if (root->leftChild == nullptr && root->rightChild == nullptr) {
        return 1;
    }
    
    return leaf(root->leftChild) + leaf(root->rightChild);
}

template <class T>
int BSTree<T>::size(){
    return size(m_root);
}

template <class T>
int BSTree<T>::size(BSTNode<T> *root) const{
    if (!root) {
        return 0;
    }
    return size(root->leftChild) + size(root->rightChild) + 1;
}

template <class T>
int BSTree<T>::height() {
    return height(m_root);
}

template <class T>
int BSTree<T>::height(BSTNode<T> *root) const{
    if (!root) {
        return -1;
    }

    int lHeight = height(root->leftChild);
    int rHeight = height(root->rightChild);
    return lHeight > rHeight ? lHeight+1 : rHeight+1;
}

template <class T>
void BSTree<T>::destroy() {
    destroy(m_root);
    m_root = nullptr;
}

template <class T>
void BSTree<T>::destroy(BSTNode<T> *root){
    //递归实现
//    if (!root) {
//        return ;
//    }
//    if (root->leftChild) {
//        destroy(root->leftChild);
//    }
//    
//    if (root->rightChild) {
//        destroy(root->rightChild);
//    }
//    
//    --m_size;
//    delete root;
//    root = nullptr;
    
    //非递归实现
    BSTNode<T> *pointer = root;
    BSTNode<T> *temp = nullptr;
    std::stack<BSTNode<T> *> aStack;
    while (!aStack.empty() || pointer) {
        if (pointer) {
            aStack.push(pointer);
            pointer = pointer->leftChild;
        }else{
            pointer = aStack.top();
            aStack.pop();
            temp = pointer;
            pointer = pointer->rightChild;
            
            std::cout << temp->data << "  ";
            delete temp;
            temp = nullptr;
        }
    }
}


#endif /* BSTree_hpp */
